//
//  BinaryTreeNode.h
//  BinaryTree
//
//  Created by DeLong Yang on 2017/7/27.
//  Copyright © 2017年 DeLong Yang. All rights reserved.
//

#import <Foundation/Foundation.h>
#import "TreeNodeProperty.h"

@class BinaryTreeNode;

typedef void (^PreSortHandler)(BinaryTreeNode *node);
typedef void (^MidSortHandler)(BinaryTreeNode *node);
typedef void (^PostSortHandler)(BinaryTreeNode *node);  // 后序查询
typedef void (^LevelSortHandler)(BinaryTreeNode *node);  // 层次 遍历


@interface BinaryTreeNode : NSObject

/**
 *  值
 */
@property (nonatomic, assign) NSInteger value;
/**
 *  左节点
 */
@property (nonatomic, strong) BinaryTreeNode *leftNode;
/**
 *  右节点
 */
@property (nonatomic, strong) BinaryTreeNode *rightNode;


/**
 *  创建二叉排序树
 *  二叉排序树：左节点值全部小于根节点值，右节点值全部大于根节点值
 *
 *  @param values 数组
 *
 *  @return 二叉树根节点
 */
+ (BinaryTreeNode *)createTreeWithValues:(NSArray *)values;


/**
 *  向二叉排序树节点添加一个节点
 *
 *  @param treeNode 根节点
 *  @param value    值
 *
 *  @return 根节点
 */
+ (BinaryTreeNode *)addTreeNode:(BinaryTreeNode *)treeNode value:(NSInteger)value;


/**
 *  二叉树中某个位置的节点（按层次遍历）
 *
 *  @param index    按层次遍历树时的位置(从0开始算)
 *  @param rootNode 树根节点
 *
 *  @return 节点
 */
+ (BinaryTreeNode *)treeNodeAtIndex:(NSInteger)index inTree:(BinaryTreeNode *)rootNode;


/**
 *  先序遍历
 *  先访问根，再遍历左子树，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)preTraverSortTree:(BinaryTreeNode *)rootNode
                  handler:(PreSortHandler )handler;

/**
 *  中序遍历
 *  先遍历左子树，再访问根，再遍历右子树
 *
 *  @param rootNode 根节点
 *  @param handler  访问节点处理函数
 */

+(void)midTraverSortTree:(BinaryTreeNode *)rootNode
                 Handler:(MidSortHandler )handler;

/**
 *  后序遍历
 *  先遍历左子树，再遍历右子树，再访问根
 *
 *  @param tree 根节点
 *  @param handler  访问节点处理函数
 */
+ (void)postTraverSortTree:(BinaryTreeNode *)tree
                   Handler:(PostSortHandler )handler;


/**
 *  层次遍历（广度优先） 层次遍历
 按照从上到下、从左到右的次序进行遍历。先遍历完一层，再遍历下一层，因此又叫广度优先遍历。需要用到队列，在OC里可以用可变数组来实现。
 *
 *  @param tree 二叉树根节点
 *  @param handler  访问节点处理函数
 */
+ (void)levelTraversSortTree:(BinaryTreeNode *)tree
                     Handler:(LevelSortHandler )handler;

/**
 *  二叉树的深度
 *
 *  @param rootNode 二叉树根节点
 *
 *  @return 二叉树的深度
 */
+ (NSInteger)depthOfTree:(BinaryTreeNode *)rootNode;

/**
 *  二叉树的宽度 二叉树的宽度定义为各层节点数的最大值。  注意是 没层节点数量的最大值
 *  首先 我们分层 然后 求出每一层 的最大值 然后 我们 比较每一层的 最大值
 *  @param tree 二叉树根节点
 *
 *  @return 二叉树宽度
 */
+ (NSInteger )widthOfTree:(BinaryTreeNode *)tree;


/**
 *  二叉树的所有节点数
 *
 *  @param rootNode 根节点
 *
 *  @return 所有节点数
 */
+ (NSInteger)numberOfNodesInTree:(BinaryTreeNode *)rootNode;

/**
 *  二叉树某层中的节点数
 *
 *  @param level    层 从 第一层开始
 *  @param rootNode 根节点
 *
 *  @return 层中的节点数
 */
+ (NSInteger)numberOfNodesOnLevel:(NSInteger)level inTree:(BinaryTreeNode *)rootNode;

/**
 *  二叉树叶子节点数  叶子节点，又叫终端节点，是左右子树都是空的节点。 很明显 叶子结点数量 = 左子树叶子结点数量
 *  加上 右子树叶子结点数量
 *
 *  @param rootNode 根节点
 *
 *  @return 叶子节点数
 */
+ (NSInteger)numberOfLeafsInTree:(BinaryTreeNode *)rootNode;

/**
 只用一次遍历算出 depth 和 二叉树直径的方法
 
 @param tree 根节点
 @return return value description
 */
+ (TreeNodeProperty *)nodePropertyOfTree:(BinaryTreeNode *)tree;

/**
 *  二叉树最大距离（直径）
 *
 *  @param rootNode 根节点
 *
 *  @return 最大距离
 */
+ (NSInteger)maxDistanceOfTree:(BinaryTreeNode *)rootNode;

/**
 查找某个 节点 到根节点点路径
 
 @param node 要查找的结点
 @param rootNode 根节点
 @return 路径上的节点
 */
+ (NSArray *)pathOfTreeNode:(BinaryTreeNode *)node
                     InTree:(BinaryTreeNode *)rootNode;

/**
 *  二叉树中两个节点最近的公共父节点
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 最近的公共父节点
 */
+ (BinaryTreeNode *)parentOfNode:(BinaryTreeNode *)nodeA andNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode;


/**
 *  二叉树中两个节点之间的路径 从查找最近公共父节点衍生出来的。
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的路径
 */
+ (NSArray *)pathFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode;


/**
 *  二叉树两个节点之间的距离 可以从两个节点之间的路径衍生出来。
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的距离（-1：表示没有找到路径）
 */
/**
 *  二叉树两个节点之间的距离 可以从两个节点之间的路径衍生出来。
 *
 *  @param nodeA    第一个节点
 *  @param nodeB    第二个节点
 *  @param rootNode 二叉树根节点
 *
 *  @return 两个节点间的距离（-1：表示没有找到路径）
 */
+ (NSInteger)distanceFromNode:(BinaryTreeNode *)nodeA toNode:(BinaryTreeNode *)nodeB inTree:(BinaryTreeNode *)rootNode;


/**
 *  翻转二叉树（又叫：二叉树的镜像）  两个左右子树先反转。然后再反转子树
 *
 *  @param rootNode 根节点  nil 值不用对调 
 *
 *  @return 翻转后的树根节点（其实就是原二叉树的根节点）
 */
+ (BinaryTreeNode *)invertBinaryTree:(BinaryTreeNode *)rootNode;


/**
 *  是否完全二叉树    我们一个一个节点 验证
 *  完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布
 *
 *  @param rootNode 根节点
 *
 *  @return YES：是完全二叉树，NO：不是完全二叉树
 */
+ (BOOL)isCompleteBinaryTree:(BinaryTreeNode *)rootNode;



/**
 *  是否满二叉树
 *  满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
 *
 *  @param rootNode 根节点
 *
 *  @return YES：满二叉树，NO：非满二叉树
 */
+ (BOOL)isFullBinaryTree:(BinaryTreeNode *)rootNode;


/**
 创建一个 满的二叉树

 @return 返回一个 随机的满的二叉树
 */
+ (BinaryTreeNode *)createFullNode;



/**
 创建一个 完全二叉树

 @return return value description
 */
+ (BinaryTreeNode *)createCompleteNode;

/**
 *  是否平衡二叉树
 *  平衡二叉树：即AVL树，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
 *
 *  @param rootNode 根节点
 *
 *  @return YES：平衡二叉树，NO：非平衡二叉树
 */
+ (BOOL)isAVLBinaryTree:(BinaryTreeNode *)rootNode;



@end
